package cbbx_sm.utils;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;


public abstract class KMeansClustering {
	public boolean debug = true;
	/**
	 * Features of the k different centroids.
	 */
	//public ArrayList<Object> centroids;
	//public ArrayList<Object> points;
	/**
	 * each place in the array list has an integer value that defines which cluster the point in the 
	 * same index at array points is assigned to.
	 */
	//public ArrayList<Short> cluster;
	//public int k;
	
	// calculate distance between vector a and b
	// needs implementation
	public abstract double dist(Object a, Object b);
	
	// calculate an approximate distance between vector a and b
	// needs implementation
	public abstract double approximateDist(Object a, Object b);
	
	// calculate centroid of a given list of vectors
	// needs implementation
	public abstract Object cent(ArrayList<Object> cluster);

	
	/**	given a list of vectors, cluster them and return the result list indicating which cluster each 
	 *	vector belongs to (cluster ID from 0 to k-1)
	 * The weird looking code that checks if the number of assignments is going down is there to account for cases where the 
	 * problem go into an infinite loop when some samples "fall" in the boundery between two centroids and keep switching
	 * between the two centroids. 
	 *
	 * @param userPoints
	 * @param k
	 * @return
	 */
	public ArrayList<Short> run(ArrayList<Object> points, int k)
	{
		//this.k = k;
		//this.points = userPoints;
		ArrayList<Object> centroids = new ArrayList<Object>();
		ArrayList<Short> cluster = new ArrayList<Short>();
		
		
		startClustering(points,k,centroids,cluster);
		if (debug) System.out.println("points: "+k+" array list length:"+points.size());
		//assignCluster();
		Integer temp;
		Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>();

		//int iterations = 0;
		while((temp=assignCluster(points,k,centroids,cluster)) != 0)
		{
			if (temp==-1){
				centroids = null;
				return null;
			}
			Integer i = ht.get(temp);
			if (i==null)
				ht.put(temp,1);
			else {
				ht.put(temp,i+1);
				if (((i>50)&&(temp<points.size()/100)))
					break;

			}
		
			if (debug) System.out.println("number of re-assignments is "+temp);
			
			ArrayList<Object> prevCentroids = new ArrayList();
			for (Object c : centroids) {
				prevCentroids.add(c);
			}
			calculateCentroids(points,k,centroids,cluster);
			
			if (changesNotSiginificant(prevCentroids, centroids, 10)) {
				break;
			}
			//iterations++;
		}
		return cluster;
	}

	

	private boolean changesNotSiginificant(
			ArrayList<Object> prevCentroids, ArrayList<Object> centroids, int dist) {

		double totalChanges = 0;
		for (int c=0; c<centroids.size(); c++) {
			totalChanges += dist(prevCentroids.get(c), centroids.get(c));
		}
		
		return (totalChanges < dist);
	}

	/**
	 * This method finds the k most distant vectors using a huristic. 
	 * First the two most far away vectors are found using an approximate
	 * distance metric.
	 * @param cluster 
	 * @param centroids 
	 * @param k 
	 * @param points 
	 */
	public void startClustering(ArrayList<Object> points, int k, ArrayList<Object> centroids, ArrayList<Short> cluster)
	{
		int i, j, c;
		double dists[][];
		double max_dist = 0;
		int m[]= new int[k];

		// phase one: find two farthest away points 

		dists = new double[points.size()][points.size()];
		for(j = 0; j < points.size(); j++)
			for(i = j+1; i < points.size(); i++)
			{
				dists[i][j] = approximateDist(points.get(i), points.get(j));
				dists[j][i] = dists[i][j];
				if(dists[j][i] > max_dist)
				{
					max_dist = dists[j][i];
					m[0] = i;
					m[1] = j;
				}
			}
		
		centroids.add(points.get(m[0]));
		centroids.add(points.get(m[1]));
		
		// phase two: keep selecting far points that are different from the previously selected ones.
		c = 2;
		while(c < k)
		{
			max_dist = 0;
			for(i = 0; i < points.size(); i++)
			{
				// avoid taking the same point.
				double distk;
				for(j = 0; j < c; j++)
					if(i == m[j])break;
				if(j < c)continue;
				
				// find the minimum dist between the current point and the previously selected points.
				distk = Math.min(dists[m[0]][i], dists[i][m[1]]);
				for(j = 2; j < c; j++)
					distk = Math.min(distk, dists[i][m[j]]);
				
				if(distk > max_dist && isDifferent(points.get(i),centroids))
				{
					max_dist = distk;
					m[c] = i;
				}
			}
			centroids.add(points.get(m[c]));
			c++;
		}
		
		
		for(i = 0; i < points.size(); i++)
		{
			cluster.add(null);
		}

	}
	
	/** Check that the new point that is about to be added is actually different from the
	 * other points that were already choosen. Fixing bug: Real data can contain equal vectors. 
	 * In this case the clustering might select two centroids that are represented by equal vectors.
	 * Then the assignment can result in less then k clusters since the first centroid among the equal 
	 * points will be always used (it is scanned first in the array of centroids and the minimun does not update.
	 * Fix: use a subset of the observations that is really distinct before the assignment.
	 *	Also, there might be another extreem case where several centroids are selected that are of equal 
	 *	distance from the rest of the points.
	 * @param feature
	 * @param centroids 
	 * @return
	 */
	private boolean isDifferent(Object feature, ArrayList<Object> centroids) {
		for (int i=0; i< centroids.size(); i++)
			if (dist(centroids.get(i), feature)==0)
				return false;
		
		return true;
	}

	/**
	 * @param cluster 
	 * @param centroids 
	 * @param k 
	 * @param points 
	 * @return the number of re-assignments in the current run. Thus, there is no stabilized set of centroids yet.
	 */
	public int assignCluster(ArrayList<Object> points, int k, ArrayList<Object> centroids, ArrayList<Short> cluster)
	{
		int i =0;
		short nk=0;
		short j = 0;
		int changes = 0;
		
		List<Integer> elementCount = new ArrayList<Integer>();
		for (int c=0; c<k; c++) {
			elementCount.add(0);
		}
		for (Short s:cluster){
			if (s!=null) {
				elementCount.set(s, elementCount.get(s)+1);				
			}
		}
		for (int eCnt:elementCount) {
			System.out.println(eCnt+";");			
		}
		
		for(i = 0; i < points.size(); i++)
		{
			double distance;
			double min_dist = Double.MAX_VALUE;
			
			for(j = 0; j < k; j++)
			{
				distance = dist(points.get(i), centroids.get(j));
				
				// Move the point if closest as well as there is room in cluster.
				if((distance < min_dist) && 
						(elementCount.get(j) < 1.1*(cluster.size()/k)))
				{
					min_dist = distance;
					nk = j;					
				}
			}
			if((cluster.get(i) == null) || nk != cluster.get(i))changes++;
			
			// Update the cluster stats.
			Short s = cluster.get(i);
			if (s!=null) {
				elementCount.set(s, elementCount.get(s) - 1);
			}
			elementCount.set(nk, elementCount.get(nk) + 1);
			
			cluster.set(i, new Short(nk));
			
		}
		if (debug) System.out.println("list size: "+cluster.size());
		
		Hashtable ht = new Hashtable();
		for (int g=0; g<cluster.size(); g++){
			ht.put(new Short(cluster.get(g)),new Integer(g));
		}
		if (debug) System.out.println("number of distinct elements in cluster: "+ht.size());
		
		// if there are less then k distinct elements, there are no enough observations in the data set to create 3 
		// samples for the 3 different states.
		if (ht.size()<k)
			return -1;
		if (debug) System.out.print("contains: ");
		for (short g=0; g<ht.size(); g++){
			if (debug) System.out.print(ht.get(g)+";");	
		}
		if (debug) System.out.println();
		
		return changes;
	}
	
	/**
	 * This method goes over the clusters created and sets centroids data-structure to be
	 * the actual centroid value of the cluster.
	 * @param cluster 
	 * @param centroids 
	 * @param k 
	 * @param points 
	 *  
	 */
	public void calculateCentroids(ArrayList<Object> points, int k, ArrayList<Object> centroids, ArrayList<Short> cluster)
	{
		// create place holders for the features of different clusters
		ArrayList<Object>[] tmp = new ArrayList[k];
		for (int i=0; i<k; i++)
			tmp[i]=new ArrayList<Object>();
		
		// place the features in the correct places in the place holders.
		for(int j = 0; j < cluster.size(); j++)
			tmp[cluster.get(j).intValue()].add(points.get(j));

		// actually compute the centroids
		for (int i=0; i<k; i++)
			centroids.set(i, cent(tmp[i]));
	}
}
